1. Field of the Invention
This invention relates to digital computers and programmable logic arrays in general, and specifically to techniques for programming a programmable logic array and for implementing a dynamically-configurable digital processor, by allowing circuit modules to be dynamically relocated within a programmable logic array.
2. Description of Related Art
Programmable logic arrays are well-known in the art. FIG. 1 illustrates a representative programmable logic array 100, intended to illustrate the general nature of programmable logic arrays and not any particular implementation of a programmable logic array. As seen in FIG. 1, programmable logic array 100 has two types of programmable elements: logic elements 101 and routing elements 102. There are also both horizontal busses 103 and vertical busses 104 carrying signals between routing elements 102, and input busses 105 and output busses 106 carrying signals to and from logic elements 101, respectively.
Each routing element 102 can be programmed to direct particular digital signals to neighboring routing elements 102 across horizontal buss 103 or vertical buss 104, and to their adjacent logic element 101. Each logic element 101 takes the digital signals on its input buss 105, performs one or more specified boolean logic operations, and places the results of the operation on its output buss 106. Logic elements 101 may also contain memory devices in addition to combination logic.
The design of a programmable logic array is equivalent to the construction of a digital circuit. The logical operations to be performed are produced by programming logic elements 101, and the logic elements 101 are connected by programming routing elements 102.
It is possible to have programmable logic arrays which have fixed functions in their logic elements, or a fixed routing between their logic elements. This often results in a programmable logic array with higher densities of functions, but with considerable less design flexibility. In any case, such programmable logic arrays are within the scope of this invention.
Early programmable logic arrays were designed either by adding a final layer of metalization to an incomplete integrated circuit, or by blowing fuse links located in key positions in the logic and routing elements. Both of these techniques resulted in fixed programmable logic arrays that could not be changed after the programmable logic arrays were configured. Recently, programmable logic arrays using switching elements controlled by static memory devices have become available. With these SRAM-based programmable logic arrays, the configuration information is written to memory elements within the programmable logic array. Those memory elements then control switching elements in key locations in the logic and routing elements of the programmable logic array. This allows for the connection (as with the metalization layer) or disconnection (as with the fuse links) of the prior programmable logic arrays, but with the ability to change the configuration of the programmable logic array at any time by simply changing the information stored in the memory elements.
Of particular interest for this invention are SRAM-based programmable logic arrays that allow the changing of only part of their configuration, without the necessity of changing the entire configuration. Such programmable logic arrays include the Configurable Logic Array (CLAy) produced by National Semiconductor, the 6200 series produced by Xilinx, and devices from Atmel.
SRAM-based programmable logic arrays are clearly more versatile than fixed programmable arrays, that are programmed by adding or removing internal wires, because SRAM-based programmable logic arrays can be conveniently reconfigured at any time. But because of the extra logic required for the SRAM-based control of the programmable logic array, they cannot achieve the density of fixed programmable logic arrays, perhaps by as much as a factor of ten. But by reprogramming the SRAM-based programmable array with functions as they are required, and not having portions of the logic array resident unless necessary, an SRAM-based programmable logic array can effectively implement the functions of a fixed programmable logic array with far more logic elements.
While there are many uses for programmable logic arrays, one important use is in the implementation of programmable digital processors that implement instruction sets optimized for particular applications. Rather than having a conventional digital computer with a general arithmetic-logic unit handling the computations, computation engines can be formed from one or more programmable logic arrays. These computation engines efficiently perform the logical and computational operations desired for the particular application. One or more programmable logic arrays can also be used to sequence the computation engines, or a single programmable logic array could contain both computation engines and their control logic.
With the advent of SRAM-based programmable logic arrays, a digital processor that can be adapted to different applications becomes possible. The programmable logic arrays implementing the processor are configured for a particular application, the operations of that application are performed, and the programmable logic arrays are then programmed for the next application. A variety of such programmable digital processors have been described in the prior art. But prior art programmable digital processors have required that the programmable logic arrays contain all computation engines and their control logic needed for a particular application while that application is being performed. This often requires a large number of logic and routing elements in the programmable logic arrays implementing the programmable digital processor, most of which are not used at any given time.
A solution would be to assemble the computation engine and its control logic for a portion of the application into an application-specific instruction module, store that module in a configuration library, and then place that application-specific instruction module into the instruction space of the programmable digital processor formed by the programmable logic arrays whenever that portion of the application is to be performed. However, that is difficult or impossible with prior art systems.
FIGS. 2a, 2b, 2c, 2d, 2e and 2f illustrate the problem with past approaches. The configuration library contains application-specific instruction modules A, B, C, and D. Modules A, B, and C are all the same size, but have been created to be placed into different locations in the programmable logic array, as indicated by their location in their depiction of the configuration library, see FIG. 2a.
FPGA system configuration 1, see FIG. 2b shows modules A, B, and C placed into the programmable logic array. FPGA system configuration 2, see FIG. 2c shows the arrangement of modules in the programmable logic array after module C is no longer needed and has been replaced with module D.
The problem occurs when module A is no longer needed, and module C is again needed. Module C cannot be placed into the programmable logic array, even though there is sufficient room left by the removal of module A, as shown in FIG. 2d. Module C must be placed into lower-right corner of the programmable, but a portion of module D is already located there and cannot be removed.
One solution would be to create an augmented configuration library, see FIG. 2e with a second version of module C, this time created to fit into the upper-left corner of the programmable logic array. The original version of module C is used along with modules A and B, and the second version of module C is used along with modules B and D. As can be seen in FPGA system configuration 4, see FIG. 2f, modules B, C (second version), and D can now reside simultaneously in the programmed logic array.
While this may work for the simple example, only requiring the creation of a second version for one module, in a complex system it would be impractical to create alternative modules. Each combination of modules possible at any time would have to be determined, and any alternative modules needed to produce that combination would have to be created. If that could not be determined, then alternatives for every possible combination of modules would have to be examined.
For efficiency considerations, not only would every possible combination of modules have to be examined, but the prior combination of modules would also have to be considered. For example, the example above shows how a second module C solves the problem when module C is replaced by module D, then module A is replaced by module C. But if module A is replaced by module D, either the original module C must be replaced with the second module C before module D is placed (requiring extra time), or a second module D, fitting in the left half (rather than the bottom half) of the programmable logic array is necessary.